/*
* leetcode 152. 乘积最大子数组
* 
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
* */
/*

* */
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Solution {
    public int maxProduct(int[] nums) {
        int n=nums.length,max=Integer.MIN_VALUE;
        int[] f=new int[n+1];
        int[] g=new int[n+1];
        f[0]=1;
        g[0]=1;
        for(int i=1;i<=n;i++){
            f[i]=Math.max(nums[i-1],Math.max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            g[i]=Math.min(nums[i-1],Math.min(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            max=Math.max(f[i],Math.max(g[i],max));
        }
        return max;
    }
}